#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#include<set>

class Solution {
public:
    bool isToeplitzMatrix(vector<vector<int>>& matrix) {
        set<pair<int,int>> S;
        for(int i = 0;i<matrix.size();++i){
            for(int j = 0;j<matrix[0].size();++j){
                int left = i;
                int right = j;
                while(left<matrix.size()&&right<matrix[0].size()&&S.find(make_pair(left,right))==S.end()){
                    S.insert(make_pair(left,right));
                    if(matrix[left][right]!=matrix[i][j]){
                        return false;
                    }
                    ++left;
                    ++right;
                }
            }
        }
        return true;
    }
};

